package top.humbleyuan.dichotomy;

/**
 * @Author: yuanhuanghui
 * @Date: 2020-08-17
 * @Time: 14:56
 * @Description: 搜索旋转有序数组
 */
public class LeetCode_33 {
    public static void main(String[] args) {
        /**
         * 二分
         */
        //m1();

        /**
         * logN二分
         */
        m2();
    }

    /**
     * 先找到旋转点，然后两个有序部分分别二分
     * 这种方法不满足logN,因为前面遍历的时候可能是O(N)的情况
     */
    public static void m1() {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};

        int rotateIndex = nums.length - 1;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] < nums[i - 1]) {
                rotateIndex = i - 1;
                break;
            }
        }

        int target = 0;
        System.out.println(nums[0] <= target ? divide(nums, 0, rotateIndex, target) :
                divide(nums, rotateIndex + 1, nums.length - 1, target));
    }

    public static int divide(int[] nums, int start, int end, int target) {
        if(nums == null || start > end) {
            return -1;
        }

        int mid = (start + end) / 2;

        if(nums[mid] == target) {
            return mid;
        }

        if(nums[mid] > target) {
            return divide(nums, start, mid - 1, target);
        } else {
            return divide(nums, mid + 1, end, target);
        }
    }

    /**
     * 1. 二分后必有一个序列有序，另一个序列的规则和原序列一样
     * 2. 判断哪个序列有序的方法是拿nums[mid]和nums[0]比较，若mid > 0则前半段有序，反之。。
     * 3. 有序的直接二分查找，无序的按原序列二分方式递归
     */
    public static void m2() {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 3;
        int res = divideM2(nums, target, 0, nums.length - 1);
        System.out.println(res);
    }

    public static int divideM2(int[] nums, int target, int start, int end) {
        if(start > end) {
            return -1;
        }

        // 为了防止溢出
        int mid = start + (end - start) / 2;
        if(nums[mid] == target) {
            return mid;
        }

        // 前半段有序
        if(nums[start] < nums[mid]) {
            // 前半段二分
            int res = divide(nums,  start, mid - 1, target);
            return res != -1 ? res : divideM2(nums, target, mid + 1, end);
        } else {
            int res = divide(nums,mid + 1, end, target);
            return res != -1 ? res : divideM2(nums, target, start, mid - 1);
        }
    }


}
